package binPack.shelf
{
	import binPack.guillotine.*;
	
	import flash.geom.Rectangle;

	public class ShelfBinPack
	{
		
		private var binWidth:int = 0;
		private var binHeight:int = 0;
		
		/// Stores the starting y-coordinate of the latest (topmost) shelf.
		private var currentY:int = 0;
		
		/// Tracks the total consumed surface area.
		private var usedSurfaceArea:uint = 0;
		
		/// If true, the following GuillotineBinPack structure is used to recover the SHELF data structure from losing space.
		private var useWasteMap:Boolean = false;
		private static var wasteMap:GuillotineBinPack;
		private var shelves:Vector.<Shelf> = new Vector.<Shelf>();
		public function ShelfBinPack(width:int=0, height:int=0,useWasteMap:Boolean=false)
		{
			Init(width, height, useWasteMap);
		}
		
		public function Init(width:int, height:int, useWasteMap_:Boolean):void
		{
			useWasteMap = useWasteMap_;
			binWidth = width;
			binHeight = height;
			
			currentY = 0;
			usedSurfaceArea = 0;
			while(shelves.length != 0 ){
				shelves.pop();
			}
			StartNewShelf(0);
			
			if (useWasteMap)
			{
				wasteMap.Init(width, height);
				var arr:Vector.<Rectangle> = wasteMap.GetFreeRectangles();
				while( arr.length ){
					arr.pop();
				}
			}
		}
		
		private function CanStartNewShelf(height:int):Boolean
		{
			var shelf:Shelf = shelves[shelves.length-1];
			return shelf.startY + shelf.height + height <= binHeight;
		}
		
		private function StartNewShelf(startingHeight:int):void
		{
			var shelf:Shelf;
			if (shelves.length > 0)
			{
				shelf = shelves[shelves.length-1];
				trace('shelf.height != 0:',shelf.height != 0);
				currentY += shelf.height;
				
				trace('currentY < binHeight:',currentY < binHeight);
			}
			
			shelf = new Shelf();
			shelf.currentX = 0;
			shelf.height = startingHeight;
			shelf.startY = currentY;
			
			trace('shelf.startY + shelf.height <= binHeight:',shelf.startY + shelf.height <= binHeight);
			shelves.push(shelf);
		}
		
		private function FitsOnShelf(shelf:Shelf, width:int, height:int, canResize:Boolean):Boolean
		{
			var shelfHeight:int = canResize ? (binHeight - shelf.startY) : shelf.height;
			if ((shelf.currentX + width <= binWidth && height <= shelfHeight) ||
				(shelf.currentX + height <= binWidth && width <= shelfHeight))
				return true;
			else
				return false;
		}
		
		private function RotateToShelf(shelf:Shelf, width:int, height:int):Object
		{	
			// If the width > height and the long edge of the new rectangle fits vertically onto the current shelf,
			// flip it. If the short edge is larger than the current shelf height, store
			// the short edge vertically.
			if ((width > height && width > binWidth - shelf.currentX) ||
				(width > height && width < shelf.height) ||
				(width < height && height > shelf.height && height <= binWidth - shelf.currentX)){
//				swap(width, height);
				var t:int = width;
				width = height;
				height = t;
			}
				
			
			return {w:width, h:height}
		}
		
		private function AddToShelf(shelf:Shelf, width:int, height:int, newNode:Rectangle):void
		{
			trace('AddToShelf 0:',FitsOnShelf(shelf, width, height, true));
			
			// Swap width and height if the rect fits better that way.
			var result:Object = RotateToShelf(shelf, width, height);
			width = result.w;
			height = result.h;
			
			// Add the rectangle to the shelf.
			newNode.x = shelf.currentX;
			newNode.y = shelf.startY;
			newNode.width = width;
			newNode.height = height;
			shelf.usedRectangles.push(newNode);
			
			// Advance the shelf end position horizontally.
			shelf.currentX += width;
			trace('AddToShelf 1:',shelf.currentX <= binWidth);
			
			// Grow the shelf height.
			shelf.height = Math.max(shelf.height, height);
			trace('AddToShelf 2:',shelf.height <= binHeight);
			
			usedSurfaceArea += width * height;
		}
		
		public function Insert(width:int, height:int, method:int):Rectangle{
			var newNode:Rectangle = new Rectangle();;
			
			// First try to pack this rectangle into the waste map, if it fits.
			if (useWasteMap){
				newNode = wasteMap.Insert(width, height, true, FreeRectChoiceHeuristic.RectBestShortSideFit, GuillotineSplitHeuristic.SplitMaximizeArea);
				if (newNode.height != 0){
					// Track the space we just used.
					usedSurfaceArea += width * height;
					return newNode;
				}
			}
			
			var shelf:Shelf;
			switch(method){
				
				case ShelfChoiceHeuristic.ShelfNextFit:		
					shelf = shelves[shelves.length-1];
					if (FitsOnShelf(shelf, width, height, true))
					{
						AddToShelf(shelf, width, height, newNode);
						return newNode;
					}
					break;
				case ShelfChoiceHeuristic.ShelfFirstFit:		
					for(var i:int = 0; i < shelves.length; ++i)
					if (FitsOnShelf(shelves[i], width, height, i == shelves.length-1))
					{
						AddToShelf(shelves[i], width, height, newNode);
						return newNode;
					}
					break;
				case ShelfChoiceHeuristic.ShelfBestAreaFit:
					// Best Area Fit rule: Choose the shelf with smallest remaining shelf area.
					var bestShelf:Shelf;
					var bestShelfSurfaceArea:uint = uint(-1);
					for(i = 0; i < shelves.length; ++i)
					{
						// Pre-rotate the rect onto the shelf here already so that the area fit computation
						// is done correctly.
						var result:Object =  RotateToShelf(shelves[i], width, height);
						width = result.w;
						height = result.h;
						if (FitsOnShelf(shelves[i], width, height, i == shelves.length-1))
						{
							var surfaceArea:uint = (binWidth - shelves[i].currentX) * shelves[i].height;
							if (surfaceArea < bestShelfSurfaceArea)
							{
								bestShelf = shelves[i];
								bestShelfSurfaceArea = surfaceArea;
							}
						}
					}
					
					if (bestShelf != null)
					{
						AddToShelf(bestShelf, width, height, newNode);
						return newNode;
					}
					break;
				
				case ShelfChoiceHeuristic.ShelfWorstAreaFit:
					// Worst Area Fit rule: Choose the shelf with smallest remaining shelf area.
//					var bestShelf:Shelf;
					bestShelfSurfaceArea = uint(-1);
					for(i = 0; i < shelves.length; ++i)
					{
						// Pre-rotate the rect onto the shelf here already so that the area fit computation
						// is done correctly.
						result = RotateToShelf(shelves[i], width, height);
						width = result.w;
						height = result.h;
						
						if (FitsOnShelf(shelves[i], width, height, i == shelves.length-1))
						{
							surfaceArea = (binWidth - shelves[i].currentX) * shelves[i].height;
							if (surfaceArea > bestShelfSurfaceArea)
							{
								bestShelf = shelves[i];
								bestShelfSurfaceArea = surfaceArea;
							}
						}
					}
					
					if (bestShelf)
					{
						AddToShelf(bestShelf, width, height, newNode);
						return newNode;
					}
					break;
				
				case ShelfChoiceHeuristic.ShelfBestHeightFit:
					// Best Height Fit rule: Choose the shelf with best-matching height.
					var bestShelfHeightDifference:int = 0x7FFFFFFF;
					for(i = 0; i < shelves.length; ++i)
					{
						// Pre-rotate the rect onto the shelf here already so that the height fit computation
						// is done correctly.
						result = RotateToShelf(shelves[i], width, height);
						width = result.w;
						height = result.h;
						
						if (FitsOnShelf(shelves[i], width, height, i == shelves.length-1))
						{
							var heightDifference:int = Math.max(shelves[i].height - height, 0);
							trace('heightDifference >= 0',heightDifference >= 0);
							
							if (heightDifference < bestShelfHeightDifference)
							{
								bestShelf = shelves[i];
								bestShelfHeightDifference = heightDifference;
							}
						}
					}
					
					if (bestShelf)
					{
						AddToShelf(bestShelf, width, height, newNode);
						return newNode;
					}
					break;
				
				case ShelfChoiceHeuristic.ShelfBestWidthFit:
					// Best Width Fit rule: Choose the shelf with smallest remaining shelf width.
					var bestShelfWidthDifference:int = 0x7FFFFFFF;
					for(i = 0; i < shelves.length; ++i)
					{
						// Pre-rotate the rect onto the shelf here already so that the height fit computation
						// is done correctly.
						result = RotateToShelf(shelves[i], width, height);
						width = result.w;
						height = result.h;
						
						if (FitsOnShelf(shelves[i], width, height, i == shelves.length-1))
						{
							var widthDifference:int = binWidth - shelves[i].currentX - width;
							trace('widthDifference >= 0:',widthDifference >= 0);
							
							if (widthDifference < bestShelfWidthDifference)
							{
								bestShelf = shelves[i];
								bestShelfWidthDifference = widthDifference;
							}
						}
					}
					
					if (bestShelf)
					{
						AddToShelf(bestShelf, width, height, newNode);
						return newNode;
					}
				break;
				
				case ShelfChoiceHeuristic.ShelfWorstWidthFit:
					// Worst Width Fit rule: Choose the shelf with smallest remaining shelf width.
					bestShelfWidthDifference = -1;
					for( i = 0; i < shelves.length; ++i)
					{
						// Pre-rotate the rect onto the shelf here already so that the height fit computation
						// is done correctly.
						result = RotateToShelf(shelves[i], width, height);
						width = result.w;
						height = result.h;
						
						if (FitsOnShelf(shelves[i], width, height, i == shelves.length-1))
						{
							var widthDifference:int = binWidth - shelves[i].currentX - width;
							trace('widthDifference >= 0',widthDifference >= 0);
							
							if (widthDifference > bestShelfWidthDifference)
							{
								bestShelf = shelves[i];
								bestShelfWidthDifference = widthDifference;
							}
						}
					}
					
					if (bestShelf)
					{
						AddToShelf(bestShelf, width, height, newNode);
						return newNode;
					}
				break;
				
			}
			
			// The rectangle did not fit on any of the shelves. Open a new shelf.
			
			// Flip the rectangle so that the long side is horizontal.
			if (width < height && height <= binWidth){
//				swap(width, height);
				var t:int = width;
				width = height;
				height = t;
			}
				
			
			if (CanStartNewShelf(height))
			{
				if (useWasteMap)
					MoveShelfToWasteMap(shelves[shelves.length-1]);
				StartNewShelf(height);
				trace(FitsOnShelf(shelves[shelves.length-1], width, height, true));
				AddToShelf(shelves[shelves.length-1], width, height, newNode);
				return newNode;
			}
			/*
			///\todo This is problematic: If we couldn't start a new shelf - should we give up
			///      and move all the remaining space of the bin for the waste map to track,
			///      or should we just wait if the next rectangle would fit better? For now,
			///      don't add the leftover space to the waste map. 
			else if (useWasteMap)
			{
			assert(binHeight - shelves.back().startY >= shelves.back().height);
			shelves.back().height = binHeight - shelves.back().startY;
			if (shelves.back().height > 0)
			MoveShelfToWasteMap(shelves.back());
			// Try to pack the rectangle again to the waste map.
			GuillotineBinPack::Node node = wasteMap.Insert(width, height, true, 1, 3);
			if (node.height != 0)
			{
			newNode.x = node.x;
			newNode.y = node.y;
			newNode.width = node.width;
			newNode.height = node.height;
			return newNode;
			}
			}
			*/
			
			// The rectangle didn't fit.
//			memset(&newNode, 0, sizeof(Rect));
			return newNode;
		}
		
		private function MoveShelfToWasteMap(shelf:Shelf):void
		{
			var freeRects:Vector.<Rectangle> = wasteMap.GetFreeRectangles();
			
			// Add the gaps between each rect top and shelf ceiling to the waste map.
			for(var i:int = 0; i < shelf.usedRectangles.length; ++i)
			{
				var r:Rectangle = shelf.usedRectangles[i];
				var newNode:Rectangle = new Rectangle();
				newNode.x = r.x;
				newNode.y = r.y + r.height;
				newNode.width = r.width;
				newNode.height = shelf.height - r.height;
				if (newNode.height > 0)
					freeRects.push(newNode);		
			}
			while(shelf.usedRectangles.length != 0)
				shelf.usedRectangles.pop();
			
			// Add the space after the shelf end (right side of the last rect) and the shelf right side. 
			var newNode:Rectangle;
			newNode.x = shelf.currentX;
			newNode.y = shelf.startY;
			newNode.width = binWidth - shelf.currentX;
			newNode.height = shelf.height;
			if (newNode.width > 0)
				freeRects.push(newNode);
			
			// This shelf is DONE.
			shelf.currentX = binWidth;
			
			// Perform a rectangle merge step.
			wasteMap.MergeFreeList();
		}
		
		/// Computes the ratio of used surface area to the bin area.
		public function Occupancy():Number
		{
			return usedSurfaceArea / (binWidth * binHeight);
		}
	}
}